package com.lz.sort;

import com.lz.common.ArrayUtils;

import java.util.Arrays;

public class QuickSort {

    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        quickSort.v0(ArrayUtils.INT_ARRAY_12);
        System.out.println(Arrays.toString(ArrayUtils.INT_ARRAY_12));
    }

    public void v0(int[] a) {
        doV1(a, 0, a.length - 1);
    }

    /**
     * 赋值3次 <href="https://blog.csdn.net/holmofy/article/details/70245895"></>
     */
    void doV0(int[] a, int low, int high) {

        int begin = low, end = high;
        int key = a[low];
        while (begin < end) {
            while (begin < end && a[end] >= key) end--;
            if (key > a[end]) {
                exch(a, begin, end);
            }
            while (begin < end && a[begin] <= key) begin++;
            if (a[begin] > key) {
                exch(a, begin, end);
            }
        }
        // exch(a, low, end);
        if (begin > low)
            doV0(a, low, begin - 1);
        if (end < high)
            doV0(a, end + 1, high);
    }

    /**
     * 赋值1次
     *
     * @param a
     * @param low
     * @param high
     */
    void doV1(int[] a, int low, int high) {
        int begin = low, end = high;
        int key = a[low];
        while (begin < end) {
            while (begin < end && a[end] >= key) end--;
            // 不是超出界限而种植
            if (begin < end) {
                a[begin] = a[end];
            }
            while (begin < end && a[begin] <= key) begin++;
            // 不是超出界限而终止
            if (begin < end) {
                a[end] = a[begin];
            }
        }
        // 最后一次的位置就是，key
        a[begin] = key;
        if (begin > low)
            doV1(a, low, begin - 1);
        if (end < high)
            doV1(a, end + 1, high);
    }

    /**
     * 算法4 其中的一个版本
     *
     * @param a
     * @param low
     * @param high
     */
    void doV2(int[] a, int low, int high) {

        if (high < low) return;
        int begin = low, end = high;
        int key = a[low];
        while (begin < end) {
            while (low < end && a[end] >= key) end--;
            while (begin < high && a[begin] <= key) begin++;
            if (begin >= end) break;
            exch(a, begin, end);
        }
        exch(a, low, end);


        if (begin > low)
            doV2(a, low, begin - 1);
        if (end < high)
            doV2(a, end + 1, high);
    }


    private void exch(int[] a, int x, int y) {
        int temp = a[x];
        a[x] = a[y];
        a[y] = temp;
    }
}
